package listbyorder.access001_100.test10;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/6 14:32
 */
public class Solution1 {

    // 方法一： 暴力递归
    public boolean isMatch(String s, String p) {
        return getAns(s, s.length(), p, p.length());
    }

    private boolean getAns(String s, int cs, String p, int cp) {
        if (cp == 0) return cs == 0;
        if (cp < 0) return false;
        if (cs == 0) {   // 这里cp肯定不是0
            if (p.charAt(cp - 1) == '*') {
                return getAns(s, cs, p, cp - 2);
            } else {
                return false;
            }
        }
        if (s.charAt(cs - 1) == p.charAt(cp - 1) || p.charAt(cp - 1) == '.') {
            return getAns(s, cs - 1, p, cp - 1);
        } else if (p.charAt(cp - 1) == '*') {
            if (cp < 2 || (p.charAt(cp - 2) != s.charAt(cs - 1) && p.charAt(cp - 2) != '.')) {
                return getAns(s, cs, p, cp - 2);
            } else {
                return getAns(s, cs, p, cp - 1) || getAns(s, cs - 1, p, cp) || getAns(s, cs, p, cp - 2);
            }
        } else {
            return false;
        }
    }
}
